{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 堆排序"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def heap_sort(vals):\n",
    "    heap = []\n",
    "    \n",
    "    # 建堆\n",
    "    for val in vals:\n",
    "        heap.append(val)\n",
    "        idx = len(heap) - 1\n",
    "        while idx > 0:\n",
    "            father_idx = (idx - 1) // 2\n",
    "            if heap[idx] >= heap[father_idx]: break\n",
    "            heap[idx], heap[father_idx] = heap[father_idx], heap[idx]\n",
    "            idx = father_idx\n",
    "    \n",
    "    # 出堆\n",
    "    sorted_vals = []\n",
    "    while heap:\n",
    "        last_idx = len(heap) - 1\n",
    "        heap[0], heap[last_idx] = heap[last_idx], heap[0]\n",
    "        sorted_vals.append(heap.pop())\n",
    "        if not heap: break\n",
    "        idx = 0\n",
    "        last_idx -= 1\n",
    "        while True:\n",
    "            min_idx = idx * 2 + 1\n",
    "            if min_idx > last_idx: break\n",
    "            right_idx = min_idx + 1\n",
    "            if right_idx <= last_idx and heap[min_idx] > heap[right_idx]:\n",
    "                min_idx = right_idx\n",
    "            if heap[idx] <= heap[min_idx]: break\n",
    "            heap[idx], heap[min_idx] = heap[min_idx], heap[idx]\n",
    "            idx = min_idx\n",
    "    return sorted_vals"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# from heapq import *\n",
    "\n",
    "# def heap_sort(vals):\n",
    "#     heapify(vals)\n",
    "#     return [heappop(vals) for i in range(len(vals))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import randint\n",
    "\n",
    "def create_test_nums():\n",
    "    global nums1, nums2, nums3, nums4, nums5, nums6\n",
    "    nums1 = [i for i in reversed(range(10000))]\n",
    "    nums2 = [i for i in range(10000)]\n",
    "    nums3 = [randint(0, 10000) for i in range(10000)]\n",
    "    nums4 = [0] * 10000\n",
    "    nums5 = [1]\n",
    "    nums6 = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "create_test_nums()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "56.6 ms ± 2.51 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit heap_sort(nums1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "38.2 ms ± 1.81 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit heap_sort(nums2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "40.7 ms ± 2.21 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit heap_sort(nums3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7.24 ms ± 163 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit heap_sort(nums4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "heap_sort(nums5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "heap_sort(nums6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 归并排序"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def merge_sort(vals):\n",
    "    length = len(vals)\n",
    "    if length <= 1: return vals\n",
    "    if length == 2: return vals if vals[0] < vals[1] else [vals[1], vals[0]]\n",
    "    mid = len(vals) // 2\n",
    "    left_vals = merge_sort(vals[:mid])\n",
    "    right_vals = merge_sort(vals[mid:])\n",
    "    sorted_vals = []\n",
    "    while left_vals or right_vals:\n",
    "        if not left_vals:\n",
    "            sorted_vals.append(right_vals.pop(0))\n",
    "            continue\n",
    "        if not right_vals:\n",
    "            sorted_vals.append(left_vals.pop(0))\n",
    "            continue\n",
    "        if left_vals[0] <= right_vals[0]:\n",
    "            sorted_vals.append(left_vals.pop(0))\n",
    "        else:\n",
    "            sorted_vals.append(right_vals.pop(0))\n",
    "    return sorted_vals"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "create_test_nums()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "33.4 ms ± 2.3 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit merge_sort(nums1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "30.6 ms ± 892 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit merge_sort(nums2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "33.7 ms ± 1.14 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit merge_sort(nums3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "29.5 ms ± 346 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit merge_sort(nums4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1]"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "merge_sort(nums5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "merge_sort(nums6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 快速排序"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import randint\n",
    "\n",
    "# 原地排序，覆盖vals，不占用额外空间\n",
    "def quick_sort(vals):\n",
    "    \n",
    "    def pivot_sort(begin, end):\n",
    "        length = end - begin\n",
    "        # 长度1和2的数组可以直接排序\n",
    "        if length <= 1: return\n",
    "        if length == 2 and vals[begin] > vals[end - 1]: vals[begin], vals[end - 1] = vals[end - 1], vals[begin]\n",
    "        # 将第一个元素和随机位置的元素交换\n",
    "        rand_idx = randint(begin, end - 1)\n",
    "        vals[begin], vals[rand_idx] = vals[rand_idx], vals[begin]\n",
    "        pivot_idx = begin\n",
    "        i = begin + 1\n",
    "        j = end - 1\n",
    "        while True:\n",
    "            # i指针向右寻找比pivot大的数\n",
    "            while i < end and vals[i] <= vals[begin]: i += 1\n",
    "            # j指针向左寻找比pivot小的数\n",
    "            while j > begin and vals[j] >= vals[begin]: j -= 1\n",
    "            # 如果i指针到达j指针右边，则将pivot的位置定位在i和j中间，这么做是为了优化有大量重复元素的情况\n",
    "            if i >= j:\n",
    "                pivot_idx = (i + j) // 2\n",
    "                break\n",
    "            # 将i和j指针的值交换\n",
    "            vals[i], vals[j] = vals[j], vals[i]\n",
    "        vals[begin], vals[pivot_idx] = vals[pivot_idx], vals[begin]\n",
    "        \n",
    "        # 递归排序左右两部分\n",
    "        pivot_sort(begin, pivot_idx)\n",
    "        pivot_sort(pivot_idx + 1, end)\n",
    "        \n",
    "    pivot_sort(0, len(vals))\n",
    "    \n",
    "    return vals"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "create_test_nums()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "25.4 ms ± 785 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit quick_sort(nums1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "25.3 ms ± 567 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit quick_sort(nums2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "27.3 ms ± 1.74 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit quick_sort(nums3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "31.6 ms ± 2.23 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit quick_sort(nums4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1]"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "quick_sort(nums5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "quick_sort(nums6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 桶排序"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bucket_sort(vals):\n",
    "    if not vals: return vals\n",
    "    # 计算最小值和最大值，确定区间\n",
    "    min_val = float('inf')\n",
    "    max_val = float('-inf')\n",
    "    for val in vals:\n",
    "        if val < min_val: min_val = val\n",
    "        if val > max_val: max_val = val\n",
    "    # 统计每个元素的出现次数\n",
    "    size = max_val - min_val + 1\n",
    "    count = [0] * size\n",
    "    for val in vals: count[val - min_val] += 1\n",
    "    # 按索引顺序输出排序结果\n",
    "    idx = 0\n",
    "    for val, time in enumerate(count):\n",
    "        if time > 0:\n",
    "            vals[idx: idx + time] = [val + min_val] * time\n",
    "            idx += time\n",
    "    return vals"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "create_test_nums()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3.77 ms ± 124 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit bucket_sort(nums1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3.78 ms ± 68.9 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit bucket_sort(nums2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3.11 ms ± 121 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit bucket_sort(nums3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.2 ms ± 43.6 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit bucket_sort(nums4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1]"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bucket_sort(nums5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bucket_sort(nums6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 33. 搜索旋转排序数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "假设按照升序排序的数组在预先未知的某个点上进行了旋转。\n",
    "\n",
    "( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。\n",
    "\n",
    "搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。\n",
    "\n",
    "你可以假设数组中不存在重复的元素。\n",
    "\n",
    "你的算法时间复杂度必须是 O(log n) 级别。\n",
    "\n",
    "示例 1:\n",
    "\n",
    "输入: nums = [4,5,6,7,0,1,2], target = 0\n",
    "输出: 4\n",
    "\n",
    "示例 2:\n",
    "\n",
    "输入: nums = [4,5,6,7,0,1,2], target = 3\n",
    "输出: -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "def search(nums, target):\n",
    "    if not nums: return -1\n",
    "    \n",
    "    # 寻找最小数的位置\n",
    "    def find_smallest_idx(left, right):\n",
    "        # 如果从小到大排列，则第一个数为最小\n",
    "        if nums[left] <= nums[right]: return nums[left]\n",
    "        # 取中间的数作为pivot\n",
    "        pivot = (left + right) // 2\n",
    "        # 比较中间数与后一个数，如果后一个数更小，则后一个数为最小\n",
    "        if nums[pivot] > nums[pivot + 1]: return pivot + 1\n",
    "        # 比较中间数与第一个数，如果第一个数更小，则表明左半段按顺序排列，应在右半段递归查找，否则在左半段递归查找\n",
    "        if nums[pivot] > nums[0]: return find_smallest_idx(pivot + 1, right)\n",
    "        return find_smallest_idx(left, pivot)\n",
    "        \n",
    "    smallest_idx = find_smallest_idx(0, len(nums) - 1)\n",
    "    \n",
    "    # 二分查找有序数列\n",
    "    def find_target(left, right):\n",
    "        mid = (left + right) // 2\n",
    "        if target == nums[mid] : return mid\n",
    "        if left == right: return -1\n",
    "        if target > nums[mid]: return find_target(mid + 1, right)\n",
    "        return find_target(left, mid - 1)\n",
    "    \n",
    "    # 如果数组没有旋转\n",
    "    if smallest_idx == 0:\n",
    "        return find_target(0, len(nums) - 1)\n",
    "    if target > nums[0]:\n",
    "        # 如果目标数比第一个数大，则在左半部分二分查找\n",
    "        return find_target(0, smallest_idx - 1)\n",
    "    elif target < nums[0]:\n",
    "        # 如果目标数比第一个数小，则在右半部分二分查找\n",
    "        return find_target(smallest_idx, len(nums) - 1)\n",
    "    return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "search([4,5,6,7,0,1,2], 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "search([4,5,6,7,0,1,2], 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "search([0,1,2,4,5,6,7], 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "search([0,1,2,4,5,6,7], 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "search([0], 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "search([], 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [],
   "source": [
    "def search2(nums, target):\n",
    "    if not nums: return -1\n",
    "    \n",
    "    def search_target(left, right):\n",
    "        if right - left < 2:\n",
    "            if nums[left] == target:\n",
    "                return left\n",
    "            if nums[right] == target:\n",
    "                return right\n",
    "            else:\n",
    "                return -1\n",
    "        \n",
    "        mid = (left + right) // 2\n",
    "        if target == nums[mid]: return mid\n",
    "        if nums[mid] > nums[left]: # 因为元素不重复，所以不用判断相等的情况\n",
    "            # 如果中间值大于左端值，说明旋转点在右半边\n",
    "            if target < nums[left] or target > nums[mid]:\n",
    "                return search_target(mid + 1, right)\n",
    "            else:\n",
    "                return search_target(left, mid - 1)\n",
    "        else:\n",
    "            # 如果中间值小于左端值，说明旋转点在左半边\n",
    "            if target > nums[right] or target < nums[mid]:\n",
    "                return search_target(left, mid - 1)\n",
    "            else:\n",
    "                return search_target(mid + 1, right)\n",
    "    \n",
    "    return search_target(0, len(nums) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "search2([4,5,6,7,0,1,2], 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "search2([4,5,6,7,0,1,2], 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "search2([7,0,1,2,3], 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "search2([0,1,2,4,5,6,7], 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "search2([0,1,2,4,5,6,7], 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "search2([0], 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "search2([0], 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "search2([], 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 81. 搜索旋转排序数组 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "假设按照升序排序的数组在预先未知的某个点上进行了旋转。\n",
    "\n",
    "( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。\n",
    "\n",
    "编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。\n",
    "\n",
    "示例 1:\n",
    "\n",
    "输入: nums = [2,5,6,0,0,1,2], target = 0\n",
    "输出: true\n",
    "\n",
    "示例 2:\n",
    "\n",
    "输入: nums = [2,5,6,0,0,1,2], target = 3\n",
    "输出: false\n",
    "\n",
    "进阶:\n",
    "\n",
    "这是 搜索旋转排序数组 的延伸题目，本题中的 nums  可能包含重复元素。\n",
    "这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [],
   "source": [
    "def search(nums, target):\n",
    "    if not nums: return False\n",
    "    \n",
    "    def search_target(left, right):\n",
    "        if right - left < 2:\n",
    "            return nums[left] == target or nums[right] == target\n",
    "        \n",
    "        mid = (left + right) // 2\n",
    "        if target == nums[mid]: return True\n",
    "        # 由于有相同的元素存在，所以如果中间值等于左端值，无法判断旋转点在哪边\n",
    "        if nums[mid] == nums[left]:\n",
    "            return search_target(mid + 1, right) or search_target(left, mid - 1)\n",
    "        elif nums[mid] > nums[left]:\n",
    "            if target < nums[left] or target > nums[mid]:\n",
    "                return search_target(mid + 1, right)\n",
    "            else:\n",
    "                return search_target(left, mid - 1)\n",
    "        else:\n",
    "            if target > nums[right] or target < nums[mid]:\n",
    "                return search_target(left, mid - 1)\n",
    "            else:\n",
    "                return search_target(mid + 1, right)\n",
    "    \n",
    "    return search_target(0, len(nums) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "search([2,5,6,0,0,1,2], 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "search([2,5,6,0,0,1,2], 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "search([2,2,2,2,2,7,0,1,1,1], 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "search([1,1,3,1,1,1,1,1,1,1], 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "search([1,3,1,1,1], 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "search([0,1,2,4,5,6,7], 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "search([0,1,2,4,5,6,7], 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "search([0], 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "search([], 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 215. 数组中的第K个最大元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。\n",
    "\n",
    "示例 1:\n",
    "\n",
    "输入: [3,2,1,5,6,4] 和 k = 2\n",
    "输出: 5\n",
    "\n",
    "示例 2:\n",
    "\n",
    "输入: [3,2,3,1,2,4,5,5,6] 和 k = 4\n",
    "输出: 4\n",
    "\n",
    "说明:\n",
    "\n",
    "你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import randint\n",
    "\n",
    "def find_kth_largest(nums, k):\n",
    "    target_idx = len(nums) - k\n",
    "    \n",
    "    def pivot_sort(left, right):\n",
    "        length = right - left + 1\n",
    "        # 将第一个元素与随机位置元素交换\n",
    "        shuffle_idx = left + randint(0, length - 1)\n",
    "        nums[left], nums[shuffle_idx] = nums[shuffle_idx], nums[left]\n",
    "        # 将第一个元素设为pivot\n",
    "        pivot = nums[left]\n",
    "        # 寻找pivot的位置，将小于pivot的元素排在左边，大于pivot的元素排在右边\n",
    "        pivot_idx = left\n",
    "        i = left + 1\n",
    "        j = right\n",
    "        while True:\n",
    "            while i <= right and nums[i] <= pivot: i += 1\n",
    "            while j > left and nums[j] >= pivot: j -= 1\n",
    "            if i >= j:\n",
    "                pivot_idx = (i + j) // 2\n",
    "                break\n",
    "            nums[i], nums[j] = nums[j], nums[i]\n",
    "        nums[left], nums[pivot_idx] = nums[pivot_idx], nums[left]\n",
    "        # 如果pivot的位置正好是第k个最大元素的位置，则返回该数\n",
    "        if pivot_idx == target_idx: return nums[target_idx]\n",
    "        if pivot_idx > target_idx:\n",
    "            # 如果pivot的位置在第k个最大元素的位置右边，则在左半段递归查找\n",
    "            return pivot_sort(left, pivot_idx - 1)\n",
    "        else:\n",
    "            # 如果pivot的位置在第k个最大元素的位置左边，则在右半段递归查找\n",
    "            return pivot_sort(pivot_idx + 1, right)\n",
    "    \n",
    "    return pivot_sort(0, len(nums) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_kth_largest([3,2,1,5,6,4], 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_kth_largest([3,2,3,1,2,4,5,5,6], 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_kth_largest([3,2,3,1,2,4,5,5,6], 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_kth_largest([3,2,3,1,2,4,5,5,6], 9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_kth_largest([3], 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 简便写法\n",
    "def find_kth_largest2(nums, k):\n",
    "    left, mid, right = [], [], []\n",
    "    for num in nums:\n",
    "        if num > nums[0]:\n",
    "            left.append(num)\n",
    "        elif num < nums[0]:\n",
    "            right.append(num)\n",
    "        else:\n",
    "            mid.append(num)\n",
    "    \n",
    "    if k <= len(left):\n",
    "        return find_kth_largest2(left, k)\n",
    "    if k <= len(left) + len(mid):\n",
    "        return mid[0]\n",
    "    return find_kth_largest2(right, k - len(left) - len(mid))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 68,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_kth_largest2([3,2,1,5,6,4], 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 69,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_kth_largest2([3,2,3,1,2,4,5,5,6], 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 70,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_kth_largest2([3,2,3,1,2,4,5,5,6], 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_kth_largest2([3,2,3,1,2,4,5,5,6], 9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 72,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_kth_largest2([3], 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 148. 排序链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。\n",
    "\n",
    "示例 1:\n",
    "\n",
    "输入: 4->2->1->3\n",
    "输出: 1->2->3->4\n",
    "\n",
    "示例 2:\n",
    "\n",
    "输入: -1->5->3->4->0\n",
    "输出: -1->0->3->4->5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [],
   "source": [
    "class ListNode(object):\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.next = None\n",
    "\n",
    "def linked_list_from_list(vals):\n",
    "    dummy = ListNode(0)\n",
    "    x = dummy\n",
    "    for val in vals:\n",
    "        x.next = ListNode(val)\n",
    "        x = x.next\n",
    "    return dummy.next\n",
    "\n",
    "def list_from_linked_list(head):\n",
    "    x = head\n",
    "    vals = []\n",
    "    while x:\n",
    "        vals.append(x.val)\n",
    "        x = x.next\n",
    "    return vals"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 快速排序算法\n",
    "def sort_list(head):\n",
    "    \n",
    "    def quick_sort(head):\n",
    "        if not head: return None, None\n",
    "        if not head.next: return head, head\n",
    "        pivot = head.val\n",
    "        dummy_left = ListNode(0)\n",
    "        dummy_right = ListNode(0)\n",
    "        left = dummy_left\n",
    "        right = dummy_right\n",
    "        mid = head\n",
    "        while mid.next:\n",
    "            if mid.next.val < pivot:\n",
    "                left.next = mid.next\n",
    "                mid.next = mid.next.next\n",
    "                left = left.next\n",
    "            elif mid.next.val > pivot:\n",
    "                right.next = mid.next\n",
    "                mid.next = mid.next.next\n",
    "                right = right.next\n",
    "            else:\n",
    "                mid = mid.next\n",
    "        left.next = None\n",
    "        right.next = None\n",
    "        \n",
    "        if dummy_left.next:\n",
    "            left_head, left_tail = quick_sort(dummy_left.next)\n",
    "            left_tail.next = head\n",
    "        else:\n",
    "            left_head = head\n",
    "        if dummy_right.next:\n",
    "            right_head, right_tail = quick_sort(dummy_right.next)\n",
    "            mid.next = right_head\n",
    "        else:\n",
    "            right_tail = mid\n",
    "        \n",
    "        return left_head, right_tail\n",
    "    \n",
    "    head, _ = quick_sort(head)\n",
    "    \n",
    "    return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4]"
      ]
     },
     "execution_count": 75,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "head = linked_list_from_list([4,2,1,3])\n",
    "head = sort_list(head)\n",
    "list_from_linked_list(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[-1, 0, 3, 4, 5]"
      ]
     },
     "execution_count": 76,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "head = linked_list_from_list([-1,5,3,4,0])\n",
    "head = sort_list(head)\n",
    "list_from_linked_list(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 3, 3, 3, 4, 5, 5, 5, 6]"
      ]
     },
     "execution_count": 77,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "head = linked_list_from_list([3,3,4,5,5,5,6,3,3,2,1])\n",
    "head = sort_list(head)\n",
    "list_from_linked_list(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[-1]"
      ]
     },
     "execution_count": 78,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "head = linked_list_from_list([-1])\n",
    "head = sort_list(head)\n",
    "list_from_linked_list(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 79,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "head = linked_list_from_list([])\n",
    "head = sort_list(head)\n",
    "list_from_linked_list(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 合并两个有序链表\n",
    "def merge(head1, head2):\n",
    "    dummy = ListNode(0)\n",
    "    node = dummy\n",
    "    while head1 and head2:\n",
    "        if head1.val <= head2.val:\n",
    "            node.next = head1\n",
    "            head1 = head1.next\n",
    "        else:\n",
    "            node.next = head2\n",
    "            head2 = head2.next\n",
    "        node.next.next = None\n",
    "        node = node.next\n",
    "    node.next = head1 if head1 else head2\n",
    "    return dummy.next\n",
    "\n",
    "# 归并排序算法\n",
    "def sort_list2(head):\n",
    "    if not head or not head.next: return head\n",
    "    \n",
    "    # 使用快慢指针找中点\n",
    "    fast = head.next\n",
    "    slow = head\n",
    "    while fast and fast.next:\n",
    "        fast = fast.next.next\n",
    "        slow = slow.next\n",
    "    \n",
    "    # 从中间切断链表\n",
    "    tail = slow\n",
    "    slow = slow.next\n",
    "    tail.next = None\n",
    "    \n",
    "    # 对左右两个链表递归排序\n",
    "    head1 = sort_list2(head)\n",
    "    head2 = sort_list2(slow)\n",
    "    \n",
    "    return merge(head1, head2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4]"
      ]
     },
     "execution_count": 81,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "head = linked_list_from_list([4,2,1,3])\n",
    "head = sort_list2(head)\n",
    "list_from_linked_list(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[-1, 0, 3, 4, 5]"
      ]
     },
     "execution_count": 82,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "head = linked_list_from_list([-1,5,3,4,0])\n",
    "head = sort_list2(head)\n",
    "list_from_linked_list(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 3, 3, 3, 4, 5, 5, 5, 6]"
      ]
     },
     "execution_count": 83,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "head = linked_list_from_list([3,3,4,5,5,5,6,3,3,2,1])\n",
    "head = sort_list2(head)\n",
    "list_from_linked_list(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[-1]"
      ]
     },
     "execution_count": 84,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "head = linked_list_from_list([-1])\n",
    "head = sort_list2(head)\n",
    "list_from_linked_list(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 85,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "head = linked_list_from_list([])\n",
    "head = sort_list2(head)\n",
    "list_from_linked_list(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cut(head, n):\n",
    "    if n <= 0: return head\n",
    "    \n",
    "    node = head\n",
    "    for i in range(n - 1):\n",
    "        if not node: break\n",
    "        node = node.next\n",
    "    \n",
    "    if not node: return node\n",
    "    \n",
    "    new_head = node.next\n",
    "    node.next = None\n",
    "    return new_head\n",
    "\n",
    "# bottom-to-up算法\n",
    "def sort_list3(head):\n",
    "    dummy = ListNode(0)\n",
    "    dummy.next = head\n",
    "    \n",
    "    length = 0\n",
    "    node = head\n",
    "    while node:\n",
    "        node = node.next\n",
    "        length +=1\n",
    "    \n",
    "    step = 1\n",
    "    while step < length:\n",
    "        node = dummy.next\n",
    "        tail = dummy\n",
    "        \n",
    "        while node:\n",
    "            # left->@->@->@->@->@->@->@->@->@\n",
    "            left = node\n",
    "            # left->@->@   right->@->@->@->@->@->@->@\n",
    "            right = cut(left, step)\n",
    "            # left->@->@   right->@->@   node->@->@->@->@->@\n",
    "            node = cut(right, step)\n",
    "\n",
    "            # dummy->@->@->@->@->@->tail->@->@->@->@->@->@   node->@->@->@->@->@\n",
    "            tail.next = merge(left, right)\n",
    "            # dummy->@->@->@->@->@->@->@->@->@->@->@->tail   node->@->@->@->@->@\n",
    "            while tail.next: tail = tail.next\n",
    "        \n",
    "        step *= 2\n",
    "    \n",
    "    return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4]"
      ]
     },
     "execution_count": 87,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "head = linked_list_from_list([4,2,1,3])\n",
    "head = sort_list3(head)\n",
    "list_from_linked_list(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[-1, 0, 3, 4, 5]"
      ]
     },
     "execution_count": 88,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "head = linked_list_from_list([-1,5,3,4,0])\n",
    "head = sort_list3(head)\n",
    "list_from_linked_list(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 3, 3, 3, 4, 5, 5, 5, 6]"
      ]
     },
     "execution_count": 89,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "head = linked_list_from_list([3,3,4,5,5,5,6,3,3,2,1])\n",
    "head = sort_list3(head)\n",
    "list_from_linked_list(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[-1]"
      ]
     },
     "execution_count": 90,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "head = linked_list_from_list([-1])\n",
    "head = sort_list3(head)\n",
    "list_from_linked_list(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 91,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "head = linked_list_from_list([])\n",
    "head = sort_list3(head)\n",
    "list_from_linked_list(head)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 969. 煎饼排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定数组 A，我们可以对其进行煎饼翻转：我们选择一些正整数 k <= A.length，然后反转 A 的前 k 个元素的顺序。我们要执行零次或多次煎饼翻转（按顺序一次接一次地进行）以完成对数组 A 的排序。\n",
    "\n",
    "返回能使 A 排序的煎饼翻转操作所对应的 k 值序列。任何将数组排序且翻转次数在 10 * A.length 范围内的有效答案都将被判断为正确。\n",
    "\n",
    " \n",
    "\n",
    "示例 1：\n",
    "\n",
    "输入：[3,2,4,1]\n",
    "输出：[4,2,4,3]\n",
    "\n",
    "解释：\n",
    "我们执行 4 次煎饼翻转，k 值分别为 4，2，4，和 3。\n",
    "\n",
    "初始状态 A = [3, 2, 4, 1]\n",
    "\n",
    "第一次翻转后 (k=4): A = [1, 4, 2, 3]\n",
    "\n",
    "第二次翻转后 (k=2): A = [4, 1, 2, 3]\n",
    "\n",
    "第三次翻转后 (k=4): A = [3, 2, 1, 4]\n",
    "\n",
    "第四次翻转后 (k=3): A = [1, 2, 3, 4]，\n",
    "\n",
    "此时已完成排序。 \n",
    "\n",
    "示例 2：\n",
    "\n",
    "输入：[1,2,3]\n",
    "输出：[]\n",
    "\n",
    "解释：\n",
    "输入已经排序，因此不需要翻转任何内容。\n",
    "请注意，其他可能的答案，如[3，3]，也将被接受。\n",
    " \n",
    "\n",
    "提示：\n",
    "\n",
    "1 <= A.length <= 100\n",
    "A[i] 是 [1, 2, ..., A.length] 的排列"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pancake_sort(vals):\n",
    "    sorted_vals = sorted(vals, reverse=True)\n",
    "    seq = []\n",
    "    for i in sorted_vals[:-1]:\n",
    "        k = vals.index(i) + 1\n",
    "        if k == len(vals): \n",
    "            vals = vals[:-1]\n",
    "            continue\n",
    "        if k > 1:\n",
    "            seq.append(k)\n",
    "            vals[:k] = vals[:k][::-1]\n",
    "        k = len(vals)\n",
    "        seq.append(k)\n",
    "        vals = vals[::-1][:-1]\n",
    "    return seq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 4, 2, 3, 2]"
      ]
     },
     "execution_count": 93,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pancake_sort([3,2,4,1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 94,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pancake_sort([1,2,3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2]"
      ]
     },
     "execution_count": 95,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pancake_sort([2,1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 96,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pancake_sort([1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 97,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pancake_sort([])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = [3,2,4,1]\n",
    "N = 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pancake_sort2(vals):\n",
    "    seq = []\n",
    "    n = len(vals)\n",
    "    flip_idx = sorted(range(1, n + 1), key = lambda i: -vals[i-1])\n",
    "    \n",
    "    for idx in flip_idx[:-1]:\n",
    "        for f in seq:\n",
    "            if idx <= f:\n",
    "                idx = f + 1 - idx\n",
    "        if idx < n: seq.extend([idx, n])\n",
    "        n -= 1\n",
    "    return seq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 4, 2, 3, 1, 2]"
      ]
     },
     "execution_count": 100,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pancake_sort2([3,2,4,1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 101,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pancake_sort2([1,2,3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2]"
      ]
     },
     "execution_count": 102,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pancake_sort2([2,1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 103,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pancake_sort2([1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 104,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pancake_sort2([])"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
